A public key cryptography system can be classified into three types: 1. a certificate-based public key cryptography system; 2. an identity-based public key cryptography system; 3. a certificateless public key cryptography system. The certificate-based public key cryptography system has a certificate management problem, and needs to consume many storage, computing, and communication resources. The identity-based public key cryptography system has an inherent key disclosure problem. The certificateless public key cryptography system resolves the foregoing two problems. A certificateless multi-proxy signature scheme is operated largely based on bilinear pairings.
Generally, certificateless multi-proxy signature (that is, multi-proxy signature based on the certificateless public key cryptography system) may be used. The certificateless multi-proxy signature does not need a certificate server to save a user's certificate, and avoids the key disclosure problem that is inherent in the identity-based public key cryptography system.
In the case of the multi-proxy signature, an original signature device is allowed to grant a signature capability of the original signature device to multiple proxy signature devices, and a valid proxy signature can be generated only when all the proxy signature devices cooperate with each other, where the proxy signature is used to represent the original signature device.
In a process of implementing the foregoing certificateless multi-proxy signature, the inventor finds that the has at least the following problem: the certificateless multi-proxy signature scheme is operated based on bilinear pairings, and the bilinear pairings involve a large computing amount and consume longer time in implementing a signature operation compared with other mechanisms. Generally, a computation cost of bilinear pairings is approximately more than 20 times that of scalar multiplication over elliptic curve group.